package com.base.dynamicprograming;

/**
 * @ClassName FindIntegers
 * @Description 600. 不含连续1的非负整数
 * 给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含连续的1的个数。
 * @Author li
 * Date 2021/9/11 22:15
 * Copyright
 **/
public class FindIntegers {
    /**
     * 给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含连续的1的个数
     * 思路：
     * 动态规划
     * 保存前一个元素的不含连续1的个数
     *
     * @param n 整数
     * @return 个数
     */
    public int findIntegers(int n) {
        if (n == 1) {
            return 1;
        }
        int pre = 1;
        for (int i = 2; i <= n; i++) {
            pre = isHasDouble1(i) ? pre + 1 : pre;
        }
        return pre;
    }

    /**
     * 求解该整数是否有连续1
     *
     * @param n 整数
     * @return
     */
    public boolean isHasDouble1(int n) {
        int pre = 0;
        do {
            int t = n % 2;
            if (pre + t == 2) {
                return true;
            }
            pre = t;
            n = n / 2;

        } while (n != 0);
        return false;
    }

    /**
     * 看不懂 呜呜呜。。。
     * @param n
     * @return
     */
    public int findIntegers1(int n) {
        int[] dp = new int[31];
        dp[0] = dp[1] = 1;
        for (int i = 2; i < 31; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        int pre = 0, res = 0;
        for (int i = 29; i >= 0; --i) {
            int val = 1 << i;
            if ((n & val) != 0) {
                res += dp[i + 1];
                if (pre == 1) {
                    break;
                }
                pre = 1;
            } else {
                pre = 0;
            }

            if (i == 0) {
                ++res;
            }
        }

        return res;
    }


}
